package java学习.算法.二叉树;

import java.util.Stack;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/6 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 二叉搜索树与双向链表 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    TreeNode cur = null;   // cur 当前节点
    TreeNode head = null; // 找到头结点后，不动
//    递归
    public TreeNode Convert(TreeNode pRootOfTree) {

        if (pRootOfTree==null){
            return  null;
        }

        // 一直 遍历到 最左边的节点（最小节点）
        Convert(pRootOfTree.left);
        if (cur==null){
            cur = pRootOfTree;
            head = pRootOfTree;
        }else {
            // 找到头之后，开始 建立双向链表
            cur.right = pRootOfTree;
            pRootOfTree.left = cur;
            cur = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }

    public TreeNode Convert1(TreeNode pRootOfTree) {
        TreeNode head = null;
        TreeNode cur = null;

        if (pRootOfTree==null){
            return  null;
        }
        Stack<TreeNode> stack = new Stack<>();
        while (pRootOfTree!=null||!stack.isEmpty()){

            while (pRootOfTree!=null){
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }

            if (head==null){
                head = pRootOfTree;
                cur = pRootOfTree;
            }else {
                cur.right = pRootOfTree;
                pRootOfTree.left = cur;
                cur = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }
}
